package LeetcodeTest_nineteen;
//123. 买卖股票的最佳时机 III
public class maxProfit
{
    public static void main(String[] args)
    {
        int price[]={5,4,3,2,1};
        System.out.println(solution.maxProfit(price));
    }
}
class solution
{
    public static int maxProfit(int[] prices)
    {
        int i,n;
        int minPrice,maxPrice,maxProfit1,maxProfit2,maxProfit;
        n=prices.length;
        minPrice=prices[0];
        maxPrice=prices[n-1];
        maxProfit=maxProfit1=maxProfit2=0;
        int profit1[]=new int[prices.length];
        int profit2[]=new int[prices.length];
        for(i=0;i<prices.length;i++)
        {
            minPrice=Math.min(prices[i],minPrice);
            maxProfit1=Math.max(prices[i]-minPrice,maxProfit1);
            profit1[i]=maxProfit1;
            maxPrice=Math.max(prices[n-i-1],maxPrice);
            maxProfit2=Math.max(maxPrice-prices[n-i-1],maxProfit2);
            profit2[n-i-1]=maxProfit2;
        }
        for(i=0;i<n-1;i++)
        {
            maxProfit=Math.max(profit1[i]+profit2[i+1],maxProfit);
        }
        return Math.max(maxProfit,prices[n-1]-prices[0]);
    }
}
/*
class solution
{
    public static int maxProfit(int[] prices)
    {
        int i,j;
        int maxProfit=0;
        boolean flag=true;
        for(i=0;i<prices.length;i++)
        {
            if(i+1<prices.length && prices[i]>prices[i+1])
            {
                flag=false;
                int num1[]=new int[i+1];
                int num2[]=new int[prices.length-i-1];
                for(j=0;j<prices.length;j++)
                {
                    if(j<=i)
                        num1[j]=prices[j];
                    else
                        num2[j-i-1]=prices[j];
                }
                if(maxProfit<partMaxProfit(num1)+partMaxProfit(num2))
                    maxProfit=partMaxProfit(num1)+partMaxProfit(num2);
            }
        }
        if(flag)
            return Math.max(maxProfit,prices[prices.length-1]-prices[0]);
        else
            return maxProfit;
    }
    public static int partMaxProfit(int num[])
    {
        if(num.length==0)
            return 0;
        int i,j,k;
        int maxProfits=0;
        for(i=0;i<num.length-1;i++)
        {
            for(j=i+1;j<num.length;j++)
            {
                if(maxProfits<num[j]-num[i])
                    maxProfits=num[j]-num[i];
            }
            k=i+1;
            while(k<num.length && num[k]>num[i])
            {
                k++;
            }
            i=k-1;
        }
        return maxProfits;
    }
}*/
